# include <stdio.h>
# include <stdlib.h>


long bezout1( long u, long v ) ;

long pgcd(long a, long b) ;

int main ()
{
	// Variables d'entrée
	unsigned long nb_bits = 0 ;
	unsigned long vect_alpha = 0 ;
	unsigned long vect_beta1 = 0 ;
	unsigned long vect_beta2 = 0 ;
	
	// Variables à calculer
	unsigned long k_beta1 = 0 ;
	unsigned long R_beta1 = 1 ;
	unsigned long e_beta1 = 0 ;
	
	unsigned long k_beta2 = 0 ;
	unsigned long R_beta2 = 1 ;
	unsigned long e_beta2 = 0 ;
	
	unsigned long e_alpha = 0 ;
	

	// Variables intermédiaires
	long i = 0 ;
	long K = 1 ;
	long M = 1 ;
	
	
	
	// On entre les valeurs nécessaires
	printf("Sous programme de calcul des valeurs de type \"generic\" : \n") ;
	printf("Nombre de bits en entrée/sortie (Dec) : ") ;
	scanf("%ld", &nb_bits) ;
	printf("Valeur du vecteur Alpha : 0x") ;
	scanf("%lX", &vect_alpha) ;
	printf("Valeur du vecteur Beta 1 : 0x") ;
	scanf("%lX", &vect_beta1) ;
	printf("Valeur du vecteur Beta 2 : 0x") ;
	scanf("%lX", &vect_beta2) ;
	
	
	
	// Vérifications élémentaires
	while( i < nb_bits ) { M = 2 * M ; i ++ ; }
	
	if( M > vect_alpha*vect_beta1*vect_beta2 )
	{	printf("ERREUR: vecteurs de base incompatibles avec la taille d'I/O.\n") ;
		exit(0) ;
	}
	
	while( K < vect_alpha)
	{ K = 2 * K ; }
	
	if ( K != vect_alpha )
	{	printf("ERREUR : vecteur Alpha pas de la forme 2^N.\n") ;
		exit(0) ;
	}
	
	if( pgcd( vect_alpha, vect_beta1 ) != 1 || pgcd( vect_beta1, vect_beta2 ) != 1 || pgcd( vect_alpha, vect_beta2) != 1 )
	{
		printf("Erreur : vecteurs non-premiers entre eux.\n") ;
		exit(1) ;
	}
	
	
	
	// RaZ des variables
	K = 0 ;

	
	//calcul pour le vecteur alpha 
	e_alpha = bezout1( vect_beta2 * vect_beta1, vect_alpha ) * vect_beta2 * vect_beta1; 
	
	// Calcul pour le vecteur Beta 1
	while( R_beta1*vect_beta1 < M ) { R_beta1 = R_beta1 * 2 ; } // Calcul de R_beta1
	
	k_beta1 = ( (-1)*bezout1( vect_beta1, R_beta1 ) ) % R_beta1 ;
	
	e_beta1 = bezout1( vect_beta2 * vect_alpha, vect_beta1 ) * vect_beta2 * vect_alpha ;
	
	
	
	// Calcul pour le vecteur Beta 2
	while( R_beta2*vect_beta2 < M ) { R_beta2 = R_beta2 * 2 ; } // Calcul de R_beta2
	
	k_beta2 = ( (-1)*bezout1( vect_beta2, R_beta2 ) ) % R_beta2 ;
	
	e_beta2 = bezout1( vect_beta1 * vect_alpha, vect_beta2 ) * vect_beta1 * vect_alpha ;
	
	
	
	// Affichage des résultats

	printf("\nPour le vecteur Alpha :\n") ;
	printf(" N = 0x%lX = %ld \n", vect_alpha, vect_alpha) ;
	printf(" e = 0x%lX = %ld \n", e_alpha, e_alpha) ;

	printf("Pour le vecteur Beta 1 :\n") ;
	printf(" N = 0x%lX = %ld \n", vect_beta1, vect_beta1) ;
	printf(" R = 0x%lX = %ld\n", R_beta1, R_beta1) ;
	printf(" k = 0x%lX = %ld\n", k_beta1, k_beta1) ;
	printf(" e = 0x%lX = %ld\n", e_beta1, e_beta1) ;
	
	printf("Pour le vecteur Beta 2 :\n") ;
	printf(" N = 0x%lX = %ld \n", vect_beta2, vect_beta2) ;
	printf(" R = 0x%lX = %ld\n", R_beta2, R_beta2) ;
	printf(" k = 0x%lX = %ld\n", k_beta2, k_beta2) ;
	printf(" e = 0x%lX = %ld\n", e_beta2, e_beta2) ;

	

}


/***************************************/

long bezout1( long a , long b)
{
	
	long a_act = a ;	// b0
	long b_act = b ;	// n0
	long t_act = 0 ;
	long t_pre = 1 ;
	long q = b_act/a_act ;
	long r = b_act - q*a_act ;
	long temp ;
	
	while( r > 0 )
	{
		temp = t_act - q*t_pre ;
		
		if( temp >= 0 ) { temp = temp % b ; }
		else { temp = b - ( (-1)*temp % b ) ; }
		
		t_act = t_pre ;
		t_pre = temp ;
		
		b_act = a_act ;
		a_act = r ;
		q = b_act/a_act ;
		r = b_act - q*a_act ;
	}
	
	if( t_pre*a % b != 1 )
	{	printf("Erreur d'intégrité du calcul.\n") ;
		// exit(1) ;
	}
	
	return( t_pre ) ;
}



/***************************************/

long pgcd(long a, long b)
{
	long c = 0 ;
	
	if ( b == 0 || a == 0 )
	{	printf("Erreur PGCD") ;
		exit(1) ;
	}
	
	if( b > a ) { c = b ; b = a ; a = c ; }
	
	while( a % b != 0 )
	{
		c = b ;
		b = a % b ;
		a = c ;
	}
	
	return(b) ;
}
